"""
a为数组，记录各点的坐标
i为起始下标
j为终止下标
"""
import math


def closet_points(a, i, j):
    m = i
    center = 0
    list_sum = 0
    if j == i:
        return i, i, math.sqrt(math.fabs(a[i]))
    if j - i == 1:
        return i, j, a[j] - a[i]
    # 1.划分为两个子问题，需要考虑三种情况
    while m <= j:
        list_sum += a[m]
        m += 1
    average = list_sum/(j - i + 1)
    for index, k in enumerate(a):
        if k > average:
            center = index
            break
    left_closet = closet_points(a, i, center - 1)
    right_closet = closet_points(a, center, j)
    # 处理第三种情况
    mid_closet = (center - 1, center, a[center] - a[center - 1])
    if mid_closet[2] > left_closet[2]:
        whole_closet = left_closet
    else:
        whole_closet = mid_closet
    if whole_closet[2] > right_closet[2]:
        whole_closet = right_closet
    return whole_closet


def sort(a, i, j):
    while i < j:
        while i < j and a[i] < a[j]:
            j -= 1
        if i < j:
            a[i], a[j] = a[j], a[i]
            i += 1
        while i < j and a[i] < a[j]:
            i += 1
        if i < j:
            a[i], a[j] = a[j], a[i]
            j -= 1
        return i


def quick_sort(a, i, j):
    if i < j:
        pivot = sort(a, i, j)
        quick_sort(a, i, pivot - 1)
        quick_sort(a, pivot + 1, j)
        return a


if __name__ == '__main__':
    list1 = [1, -9, 2, 4, -3]
    print(quick_sort(list1, 0, 4))
    print(closet_points(list1, 0, len(list1) - 1))
